package test.n00000;

public class Problem00052 {
    public static void main(String[] args) {
        println("babad");
        println("cbbd");
        println("bb");
        println("babad");
        println("aacabdkacaa");
    }

    public static void println(String s) {
        Solution ss = new Solution();
        System.out.println(s + "," + ss.longestPalindrome(s));
    }

    public static class Solution {
        /**
         * 给你一个字符串 s，找到 s 中最长的回文子串。
         * <p>
         * 解题方法:(动态规划+状态转移)
         * P(i,j) = P(i+1, j-1) & (Si == Sj)
         *
         * @param s
         * @return
         */
        public String longestPalindrome(String s) {
            if (s.length() < 2) {
                return s;
            }
            int maxLen = 1;
            int begin = 0;

            int len = s.length();

            boolean[][] positions = new boolean[s.length()][s.length()];
            for (int i = 0; i < len; i++) {
                positions[i][i] = true;
            }

            for (int L = 2; L <= len; L++) {
                for (int i = 0; i < len; i++) {
                    int j = L + i - 1;
                    if (j >= len) {
                        break;
                    }

                    if (s.charAt(i) == s.charAt(j)) {
                        if (j - i < 3) {
                            positions[i][j] = true;
                        } else {
                            positions[i][j] = positions[i + 1][j - 1];
                        }
                    } else {
                        positions[i][j] = false;
                    }

                    if (positions[i][j] == true && j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }
    }
}
